package com.lei.sort;

import com.lei.linearsearch.ArrayGenerator;

import java.util.Random;

/**
 * @Author LeiXiaoLei
 * @Date 2022/8/11 16:31
 * @Version 1.0
 */
public class QuickSort {

    private QuickSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] arr) {
        Random random = new Random();
        innerSort(arr, 0, arr.length - 1, random);
    }

    private static <E extends Comparable<E>> void innerSort(E[] arr, int l, int r, Random random) {
        if (l >= r) return;
        if (r - l < 16) {
            InsertionSort.sort4(arr, l, r);
            return;
        }
        //双路快排
        int p = partition2(arr, l, r, random);
        innerSort(arr, l, p - 1, random);
        innerSort(arr, p + 1, r, random);
    }

    //双路快排
    private static <E extends Comparable<E>> int partition2(E[] arr, int l, int r, Random random) {
        int p = (l + random.nextInt(r - l + 1));
        swap(arr, l, p);
        int i = l + 1, j = r;
        while (true) {
            while (i <= j && arr[i].compareTo(arr[l]) < 0) {
                i++;
            }
            while (j >= i && arr[j].compareTo(arr[l]) > 0) {
                j--;
            }
            if (i >= j) break;
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, l, j);
        return j;
    }

    //三路快排
    private static <E extends Comparable<E>> void innerSort3(E[] arr, int l, int r, Random random) {
        if (l >= r) return;
        int p = l + random.nextInt(r - l + 1);
        swap(arr, l, p);
        int lt = l, i = l + 1, gt = r + 1;
        while (i < gt) {
            if (arr[i].compareTo(arr[l]) < 0) {
                lt++;
                swap(arr, i, lt);
                i++;
            } else if (arr[i].compareTo(arr[l]) > 0) {
                gt--;
                swap(arr, i, gt);
            } else {
                i++;
            }
        }
        swap(arr, l, lt);
        innerSort3(arr, l, lt - 1, random);
        innerSort3(arr, gt, r, random);
    }

    private static <E extends Comparable<E>> int partition(E[] arr, int l, int r, Random random) {
        int p = (l + random.nextInt(r - l + 1));
        swap(arr, l, p);
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i].compareTo(arr[l]) < 0) {
                j++;
                swap(arr, i, j);
            }
        }
        swap(arr, l, j);
        return j;
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
        int[] dataSize = {10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
        for (int n : dataSize) {
            Integer[] arr = ArrayGenerator.generatorRandomArray(n, n);
            SortingHelper.sortTest(QuickSort.class, arr);
        }
//        int n = 10000000;
//        Integer[] arr = ArrayGenerator.generatorRandomArray(n, 1);
//        SortingHelper.sortTest(QuickSort.class, arr);
    }
}
